#include "sw_dlink.h"

/**
 * @brief 初始化链表
 * 
 * @return dlink* 链表
 */
dlink* dlink_init()
{
    dlink* head = (dlink*)malloc(sizeof(dlink));
    head->next = head;
    head->prev = head;
    return head;
}

/**
 * @brief 拷贝初始化链表
 * 
 * @param head 链表
 * @param size 节点大小
 * @return dlink* 新链表
 */
dlink* dlink_init_from_link(dlink *head, size_t size)
{
    dlink* new_link = dlink_init();
    dlink* cur = NULL;

    dlink_foreach(cur, head) {
        dlink *tmp = (dlink*)malloc(size);
        memcpy(tmp, cur, size);
        dlink_push_back(new_link, tmp);
    }

    return new_link;
}

/**
 * @brief 拷贝[begin, end)初始化链表
 * 
 * @param begin 
 * @param end 
 * @param size 节点大小
 * @return dlink* 新链表
 */
dlink* dlink_init_from_range(dlink *begin, dlink* end, size_t size)
{
    dlink* new_link = dlink_init();
    dlink* cur = begin;

    for(cur = begin; cur != end; cur = cur->next) {
        dlink *tmp = (dlink*)malloc(size);
        memcpy(tmp, cur, size);
        dlink_push_back(new_link, tmp);
    }

    return new_link;
}

/**
 * @brief 将[first, last)内的所有节点移动到position之前
 * 
 * @param position 
 * @param first 
 * @param last 
 */
static void transfer(dlink* position, dlink* first, dlink* last)
{
    if (position != last) {
        last->prev->next = position;
        first->prev->next = last;
        position->prev->next = first;
        dlink* tmp = position->prev;
        position->prev = last->prev;
        last->prev = first->prev;
        first->prev = tmp;
    }
}

/**
 * @brief 放入链表头
 * 
 * @param head 链表
 * @param data 节点
 */
void dlink_push_front(dlink* head, dlink *data)
{
    data->next = head->next;
    data->prev = head;
    head->next->prev = data;
    head->next = data;
}

/**
 * @brief 放入链表尾
 * 
 * @param head 链表
 * @param data 节点
 */
void dlink_push_back(dlink* head, dlink *data)
{
    data->next = head;
    data->prev = head->prev;
    head->prev->next = data;
    head->prev = data;
}

/**
 * @brief 放入链表index位置
 * 
 * @param head 链表
 * @param data 节点
 * @param index 放入的位置
 */
void dlink_push_index(dlink* head, dlink *data, int index)
{
    int i;
    dlink* cur = head->next;
    for (i = 0; i < index && cur != head; i++) {
        cur = cur->next;
    }
    dlink_insert_front(cur, data);
}

/**
 * @brief 移除链表第一个节点
 * 
 * @param head 链表
 * @return dlink* 移除的节点
 */
dlink* dlink_pop_front(dlink *head)
{
    if (head->next == head) return NULL;
    dlink *cur = head->next;
    head->next = head->next->next;
    head->next->prev =  head;
    cur->prev = NULL;
    cur->next = NULL;
    return cur;
}

/**
 * @brief 移除链表最后一个节点
 * 
 * @param head 链表
 * @return dlink* 移除的节点
 */
dlink* dlink_pop_back(dlink *head)
{
    if (head->prev == head) return NULL;
    dlink *cur = head->prev;
    head->prev = head->prev->prev;
    head->prev->next = head;
    cur->next = NULL;
    cur->prev = NULL;
    return cur;
}

/**
 * @brief 清空链表
 * 
 * @param head 链表
 * @param destroy 每个节点释放前回调
 * @param arg 回调参数
 */
void dlink_clear(dlink *head, dlink_one_cb destroy, void* arg)
{
    dlink* cur = head->next;
    dlink* temp = nullptr;
    while(cur != head) {
        temp = cur;
        cur = cur->next;
        if (destroy != nullptr) {
            destroy(temp, arg);
        }
        free(temp);
    }
    head->next = head;
    head->prev = head;
}

/**
 * @brief 释放链表
 * 
 * @param head 链表
 * @param destroy 每个节点释放前回调
 * @param arg 回调参数
 */
void dlink_destory(dlink *head, dlink_one_cb destroy, void* arg)
{
    dlink_clear(head, destroy, arg);
    free(head);
}

/**
 * @brief 移除并释放所有满足destroy的节点
 * 
 * @param head 链表
 * @param destroy return true to release the node， if there is a pointer inside the node release it here
 * @param arg 参数
 */
void dlink_ifdestory(dlink *head, dlink_one_cb destroy, void* arg)
{
    dlink *cur, *ret = nullptr;
    dlink_foreach(cur, head) {
        if ((destroy != nullptr) && destroy(cur, arg)) {
            ret = cur;
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            cur = ret->prev;
            free(ret);
        }
    }
    return ;
}

/**
 * @brief 查找首个满足条件的节点
 * 
 * @param head 链表
 * @param find 条件函数
 * @param arg 参数
 * @return dlink* null：没有发现
 */
dlink* dlink_find_first(dlink *head, dlink_one_cb find, void* arg)
{
    dlink* cur;
    dlink_foreach(cur, head) {
        if (find(cur, arg)) {
            return cur;
        }
    }
    return nullptr;
}

/**
 * @brief 查找最后一个满足条件的节点
 * 
 * @param head 链表
 * @param find 查找条件
 * @param arg 参数
 * @return dlink* null：没有发现
 */
dlink* dlink_find_last(dlink *head, dlink_one_cb find, void* arg)
{
    dlink *cur, *ret = nullptr;
    dlink_foreach(cur, head) {
        if (find(cur, arg)) {
            ret = cur;
        }
    }
    return ret;
}

/**
 * @brief 将node节点从head链表中移除
 * 
 * @param head 链表头
 * @param node 要移除的节点
 * @return dlink* null：node不在链表中，other 移除的节点
 */
dlink* dlink_delete(dlink *head, dlink* node)
{
    dlink *cur, *ret = nullptr;
    dlink_foreach(cur, head) {
        if (cur == node) {
            ret = cur;
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            break;
        }
    }
    return ret;
}

/**
 * @brief 删除首个满足del条件的节点
 * 
 * @param head 链表头
 * @param del 删除条件
 * @param arg del参数
 * @return dlink* 删除的节点
 */
dlink* dlink_delete_first(dlink *head, dlink_one_cb del, void* arg)
{
    dlink *cur, *ret = nullptr;
    dlink_foreach(cur, head) {
        if (del(cur, arg)) {
            ret = cur;
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            break;
        }
    }
    return ret;
}

/**
 * @brief 删除最后一个满足del条件的节点
 * 
 * @param head 链表头
 * @param del 删除条件
 * @param arg del参数
 * @return dlink* 删除的节点
 */
dlink* dlink_delete_last(dlink *head, dlink_one_cb del, void* arg)
{
    dlink *cur, *ret = nullptr;
    dlink_foreach(cur, head) {
        if (del(cur, arg)) {
            ret = cur;
        }
    }
    if (ret != nullptr) {
        ret->prev->next = ret->next;
        ret->next->prev = ret->prev;
    }
    return ret;
}

/**
 * @brief 获取链表有效长度
 * 
 * @param head 链表头
 * @return int 链表有效长度
 */
int dlink_get_size(dlink *head)
{
    dlink *cur;
    int ret = 0;
    dlink_foreach(cur, head) {
        ret++;
    }
    return ret;
}

/**
 * @brief 判断链表节点总数是否为0
 * 
 * @param head 链表
 * @return true 链表为空
 * @return false 链表不为空
 */
bool dlink_empty(dlink *head)
{
    return head->next == head;
}

/**
 * @brief 获取链表首个节点
 * 
 * @param head 
 * @return dlink* 
 */
dlink* dlink_begin(dlink *head)
{
    if (dlink_empty(head)) {
        return NULL;
    }
    return head->next;
}

/**
 * @brief 获取链表最后一个节点的下一个节点
 * 
 * @param head 
 * @return dlink* 
 */
dlink* dlink_end(dlink *head)
{
    return head;
}

/**
 * @brief 获取链表首个节点
 * 
 * @param head 
 * @return dlink* 
 */
dlink* dlink_front(dlink *head)
{
    if (dlink_empty(head)) {
        return NULL;
    }
    return head->next;
}

/**
 * @brief 获取链表最后一个节点
 * 
 * @param head 
 * @return dlink* 
 */
dlink* dlink_back(dlink *head)
{
    if (dlink_empty(head)) {
        return NULL;
    }
    return head->prev;
}

/**
 * @brief 将head内容放入position之前， 
 * @note 执行后head is empty, position不能在head内
 * @param position 
 * @param head 
 */
void dlink_splice_head(dlink *position, dlink *head)
{
    if (!dlink_empty(head)) {
        transfer(position, dlink_begin(head), dlink_end(head));
    }
}

/**
 * @brief 将node节点放入position之前
 * @note position node必须属于同一个链表
 * @param position 
 * @param node 
 */
void dlink_splice_node(dlink *position, dlink *node)
{
    dlink* next = node->next;
    if (position == node || position == next) return;
    transfer(position, node, next);
}

/**
 * @brief 将[first, last)范围内所有节点放入position所指位置之前
 * @note position 不能在[first, last)范围内，左闭右开区间
 * @param position 
 * @param first 
 * @param last 
 */
void dlink_splice_range(dlink *position, dlink *first, dlink* last)
{
    if (first != last) {
        transfer(position, first, last);
    }
}

/**
 * @brief head2合并到head1上
 * @note 合并后head2为空,head1和head2都为递增或者递减
 * @param head1 
 * @param head2 
 * @param cmp 比较函数
 * @param arg 参数
 */
void dlink_merge(dlink *head1, dlink *head2, dlink_tow_cb cmp, void * arg)
{
    if (dlink_empty(head2)) {
        return;
    }
    if (dlink_empty(head1)) {
        head1->prev = head2->prev;
        head1->next = head2->next;
        head2->next->prev = head1;
        head2->prev->next = head1;
        head2->next = head2;
        head2->prev = head2;
        return;
    }

    dlink *first1 = dlink_begin(head1);
    dlink *first2 = dlink_begin(head2);
    dlink *last1 = dlink_end(head1);
    dlink *last2 = dlink_end(head2);

    while (first1 != last1 && first2 != last2) {
        if (cmp(first1, first2, arg) > 0) {
            dlink* next = first2;
            next = next->next;
            transfer(first1, first2, next);
            first2 = next;
        } else {
            first1 = first1->next;
        }
    }
    if (first2 != last2) {
        transfer(last1, first2, last2);
    }
}

/**
 * @brief 逆向重置链表
 * 
 * @param head 
 */
void dlink_reverse(dlink *head)
{
    /* 如果只有0个或1个元素不进行任何操作 */
    if (head->next == head || head->next->next == head) {
        return;
    }
    dlink* first = dlink_begin(head);
    first = first->next;
    while (first != dlink_end(head))
    {
        dlink* old = first;
        first = first->next;
        transfer(dlink_begin(head), old, first);
    }
}

/**
 * @brief 交换head1和head2内容
 * 
 * @param head1 
 * @param head2 
 */
void dlink_swap(dlink *head1, dlink *head2)
{
    if (dlink_empty(head1) && dlink_empty(head2)) {
        return;
    }
    if (dlink_empty(head1)) {
        head1->prev = head2->prev;
        head1->next = head2->next;
        head2->next->prev = head1;
        head2->prev->next = head1;
        head2->next = head2;
        head2->prev = head2;
    } else if (dlink_empty(head2)) {
        head2->prev = head1->prev;
        head2->next = head1->next;
        head1->next->prev = head2;
        head1->prev->next = head2;
        head1->next = head1;
        head1->prev = head1;
    } else {
        dlink* tmp1 = head1->next;
        dlink* tmp2 = head1->prev;

        head1->next = head2->next;
        head1->prev = head2->prev;
        head2->next->prev = head1;
        head2->prev->next = head1;

        head2->next = tmp1;
        head2->prev = tmp2;
        tmp1->prev = head2;
        tmp2->next = head2;
    }    
}

void dlink_sort(dlink* head, dlink_tow_cb cmp, void * arg)
{
    /* 如果只有0个或1个元素不进行任何操作 */
    if (head->next == head || head->next->next == head) {
        return;
    }
    int max = 0;
    /* 一些新的dlink，作为中介数存放区 */
    dlink* carry = dlink_init();
    dlink* counter[64];
    int i = 0;
    for (i = 0; i < 64; i++) {
        counter[i] = dlink_init();
    }
    int fill = 0;
    while(!dlink_empty(head)) {
        if (dlink_empty(carry)) {
            dlink_push_front(carry, dlink_pop_front(head));
        } else {
            dlink_splice_node(dlink_begin(carry), dlink_begin(head));
        }
        i = 0;
        while(i < fill && !dlink_empty(counter[i])) {
            dlink_merge(counter[i], carry, cmp, arg);
            dlink_swap(carry, counter[i++]);
        }
        dlink_swap(carry, counter[i]);
        if (i == fill) ++fill;
        if (fill > max) max = fill;
        // printf("i = %d, fill = %d\n", i, fill);
    }
    for (i = 1; i < fill; ++i) {
        dlink_merge(counter[i], counter[i - 1], cmp, arg);
    }
    dlink_swap(head, counter[fill - 1]);

    free(carry);
    for (i = 0; i < 64; i++) {
        free(counter[i]);
    }
    printf("max fill = %d\n", max);
}
